package com.mdnote.practice.tire;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/23
 * @description 实现 Trie (前缀树)
 */
public class LeetCode208 {

    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("app");
        trie.insert("apple");
        System.out.println(trie.search("applee")); // 返回 true

    }

    private static class Trie {

        private TreeNode root;

        /** Initialize your data structure here. */
        public Trie() {
            this.root = new TreeNode();
        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            // 插入操作
            char[] charArray = word.toCharArray();
            TreeNode cur = root;
            // 遍历单词的字母
            for (int i = 0; i < charArray.length; i++) {
                // 设置第i个字母到树种
                if (cur.getChild(charArray[i]) == null) {
                    cur.setChild(charArray[i]);
                }
                // 向下走
                cur = cur.getChild(charArray[i]);
            }
            // 最后标记一下已经到最后了
            cur.setEnd(true);
        }

        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TreeNode cur = root;
            char[] charArray = word.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                // 当前节点不能为空
                if (cur == null) {
                    return false;
                }
                // 获取下一个节点
                cur = cur.getChild(charArray[i]);
                // 判断是否匹配完成,如果搜索的字符串比较长cur有可能为null
                if (i == charArray.length - 1 && cur != null && cur.isEnd()) {
                    return true;
                }

            }
            // 看看是不是刚好匹配到最后了
            return cur != null && cur.isEnd();
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TreeNode cur = root;
            char[] charArray = prefix.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                // 当前节点不能为空
                if (cur == null) {
                    return false;
                }
                // 获取下一个节点
                cur = cur.getChild(charArray[i]);
                // 找得到就行
            }
            // 如果下面还有东西说明是前缀呀
            return cur != null;
        }
    }

    private static class TreeNode {

        private TreeNode[] children;
        private boolean isEnd;
        private int size = 26;

        public TreeNode() {
            children = new TreeNode[size];
        }

        private TreeNode getChild(char c) {
            return this.children[c - 'a'];
        }
        private void setChild(char c2) {
            this.children[c2 - 'a'] = new TreeNode();
        }
        private boolean isEnd() {
            return this.isEnd;
        }

        public void setEnd(boolean end) {
            isEnd = end;
        }

    }
}
